home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 26
/
Cream of the Crop 26.iso
/
program
/
snip9707.zip
/
BITCNT_4.C
< prev
next >
Wrap
C/C++ Source or Header
|
1997-07-05
|
2KB
|
83 lines
/* +++Date last modified: 05-Jul-1997 */
/*
** BITCNT_4.C - Recursive bit counting functions using table lookup
**
** public domain by Bob Stout
*/
#include "bitops.h" /* from Snippets */
static char bits[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, /* 0 - 15 */
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 16 - 31 */
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 32 - 47 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 48 - 63 */
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 64 - 79 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 80 - 95 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 96 - 111 */
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 112 - 127 */
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, /* 128 - 143 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 144 - 159 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 160 - 175 */
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 176 - 191 */
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, /* 192 - 207 */
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 208 - 223 */
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, /* 224 - 239 */
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 /* 240 - 255 */
};
/*
** Count bits in each nybble
**
** Note: Only the first 16 table entries are used, the rest could be
** omitted.
*/
int CDECL ntbl_bitcnt(long x)
{
int cnt = bits[(int)(x & 0x0000000FL)];
if (0L != (x >>= 4))
cnt += ntbl_bitcnt(x);
return cnt;
}
/*
** Count bits in each byte
*/
int CDECL btbl_bitcnt(long x)
{
int cnt = bits[ ((char *)&x)[0] & 0xFF ];
if (0L != (x >>= 8))
cnt += btbl_bitcnt(x);
return cnt;
}
#ifdef TEST
#include <stdlib.h>
#include "snip_str.h" /* For plural_text() macro */
main(int argc, char *argv[])
{
long n;
while(--argc)
{
int i;
n = atol(*++argv);
i = btbl_bitcnt(n);
printf("%ld contains %d bit%s set\n",
n, i, plural_text(i));
}
return 0;
}
#endif /* TEST */